// m

// 给定一个二叉搜索树的根节点root，以及一个值key
// 要求从二叉搜索树中删除key对应的节点，并保证删除后的树仍是二叉搜索树，要求算法时间复杂度为O(h),h为树的高度，最后返回二叉搜索树的根节点

// 解题思路；递归

// 删除分两个步骤，查找和删除，查找通过递归，删除需要考虑情况

function deleteNode(root, key) {
    if (!root) {
        return root
    }
    if (root.val > key) {
        root.left = deleteNode(root.left, key)
        return root
    } else if (root.val < key) {
        root.right = deleteNode(root.right, key)
        return root
    } else {
        if (!root.left) {
            return root.right
        } else if (!root.right) {
            return root.left
        } else {
            // 找右子树最左侧的叶子节点
            let curr = root.right
            while (curr.left) {
                curr = curr.left
            }
            curr.left = root.left
            return root.right
        }
    }
}